package datastructures.sparse;

import java.util.Arrays;

/**
 * 稀疏数组Demo
 *
 * @author hck
 */
public class SparseArray {
    public static void main(String[] args) {
        int[][] sourceArr = new int[][]{
                {0, 0, 0, 1, 0, 0, 2, 0, 0},
                {0, 7, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 9, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 3, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 1},
                {0, 2, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 5, 0, 0, 0, 0}
        };
        System.out.println(">>>>>>>> source arr:");
        print2DArr(sourceArr);
        System.out.println(">>>>>>>> parse to sparse arr:");
        int[][] sparseArr = toSparseArray(sourceArr);
        print2DArr(sparseArr);
        System.out.println(">>>>>>>> parse sparse arr to source:");
        sourceArr = sparseArrayRecovery(sparseArr);
        print2DArr(sourceArr);
    }


    /**
     * 普通二维数组转换为稀疏数组
     *
     * @param source source
     * @return sparse array
     */
    private static int[][] toSparseArray(int[][] source) {
        //  计算二维数组总size
        int total = 0;
        //  行
        int raw = source.length;
        //  列
        int col = source[0].length;
        for (int[] temp : source) {
            for (int i : temp) {
                if (i != 0) {
                    total++;
                }
            }
        }
        //  初始化稀疏数组
        int[][] sparseArr = new int[total + 1][3];
        sparseArr[0][0] = raw;
        sparseArr[0][1] = col;
        sparseArr[0][2] = total;
        int sparseRaw = 1;
        for (int raw1 = 0; raw1 < source.length; raw1++) {
            for (int col1 = 0; col1 < source[raw1].length; col1++) {
                if (source[raw1][col1] != 0) {
                    sparseArr[sparseRaw][0] = raw1;
                    sparseArr[sparseRaw][1] = col1;
                    sparseArr[sparseRaw][2] = source[raw1][col1];
                    sparseRaw++;
                }
            }
        }
        return sparseArr;
    }

    /**
     * 稀疏数组还原为原始数组
     *
     * @param sparse sparse array
     * @return source array
     */
    private static int[][] sparseArrayRecovery(int[][] sparse) {
        int rawLength = sparse[0][0];
        int colLength = sparse[0][1];
        //  初始化原始索引
        int[][] source = new int[rawLength][colLength];
        for (int i = 1; i < sparse.length; i++) {
            int raw = sparse[i][0];
            int col = sparse[i][1];
            int val = sparse[i][2];
            source[raw][col] = val;
        }
        return source;
    }

    /**
     * 打印二维数组
     *
     * @param sourceArr 待打印数组
     */
    private static void print2DArr(int[][] sourceArr) {
        for (int[] temp : sourceArr) {
            System.out.println(Arrays.toString(temp));
        }
    }
}
